package leetcode.list;

/**
 * 160. 相交链表
 */
public class _160 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(8);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;

        ListNode nodeA4 = new ListNode(4);
        ListNode nodeA1 = new ListNode(1);
        nodeA4.next=nodeA1;

        ListNode nodeB5 = new ListNode(5);
        ListNode nodeB0 = new ListNode(0);
        ListNode nodeB1 = new ListNode(1);
        nodeB5.next=nodeB0;
        nodeB0.next=nodeB1;



        nodeA1.next = node1;
        nodeB1.next = node1;

        ListNode listNode = getIntersectionNode(nodeA4, nodeB5);

        System.out.println("listNode = " + listNode);
        System.out.println("listNode.val = " + listNode.val);

    }



    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode temp = headA;

        int lengthA = 1;
        int lengthB = 1;
        // 计算A的长度
        while (temp.next != null) {
            lengthA++;
            temp = temp.next;
        }
        // 计算B的长度
        temp = headB;
        while (temp.next != null) {
            lengthB++;
            temp = temp.next;
        }

        System.out.println("lengthA = " + lengthA);
        System.out.println("lengthB = " + lengthB);

        // AB指针
        ListNode tempA = headA;
        ListNode tempB = headB;

        if (lengthA != lengthB) {
            if (lengthA > lengthB) {
                for (int i = 0; i < Math.abs(lengthA - lengthB); i++) {
                    tempA = tempA.next;
                }
            } else {
                for (int i = 0; i < Math.abs(lengthA - lengthB); i++) {
                    tempB = tempB.next;
                }
            }
        }

        while (tempA != null && tempB != null) {
            if (tempA == tempB) {
                return tempA;
            }
            tempA = tempA.next;
            tempB = tempB.next;
        }
        // 无相同节点
        return null;
    }


    // A+B = B+A 相当于两个链表连在一起 先走一遍相交部分 再把不相同的部分走掉 剩余的就是第二遍的共同部分了
    public ListNode getIntersectionNodeStd(ListNode headA, ListNode headB) {
        ListNode h1 = headA, h2 = headB;

        while (h1 != h2) {
            h1 = h1.next;
            h2 = h2.next;

            if (h1 == null && h2 == null) break;
            if (h1 == null) h1 = headB;
            if (h2 == null) h2 = headA;
        }

        return h1;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


}
